/**
 * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
 *
 * 只使用数字1到9
 * 每个数字 最多使用一次
 * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 *
 *https://leetcode.cn/problems/combination-sum-iii/description/
 */
class CombinationSum3 {
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(k,0,n,new LinkedList<>(),0,1);
        return ret;
    }
    public void backtrack(int k,int count,int n,Deque<Integer> qu,int target,int start) {
        if(k==count) {
            if(target==n) {
                ret.add(new ArrayList<>(qu));
                
            }
            return;
        }
        for(int i=start;i<=9;i++) {
            if(target+i>n) {
                continue;
            }
            qu.addLast(i);
            backtrack(k,count+1,n,qu,target+i,i+1);
            qu.removeLast();
        }
    }
}